#include "BTreeNode.h"
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
	
	if ( pf.read(pid, m_buffer) < 0 )
	{
		cout << "Error reading from the page file" << endl;
		exit(1);
	} 
	
	return 0; 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
	
	if ( pf.write(pid, m_buffer) < 0)
	{
		cout << "Error writing to the page file" << endl;
		exit(1);
	}
	
	return 0; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	int count = 0;
	
	// Point the entry struct to the buffer and parse it til we hit NULL
	entryStruct *entry = (entryStruct *)m_buffer;
	while ( entry->rid.pid != 0 && entry->rid.sid != 0 && entry->key != 0)
	{
		count++;
		entry++;
	}

	return count; 
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	// Point the entryStruct to the buffer and parse through it
	// if key > the entry's key, move on
	// else, insert to the next position in the buffer
	entryStruct *entry = (entryStruct *)m_buffer;
	int entry_num = 0;

	while ( entry->rid.pid != 0 && entry->rid.sid != 0 && entry->key != 0)
	{
		if ( key >= entry->key)
		{
			entry++;
			entry_num++;
		}
		else
			break;
	}

	// check to see if we need to rearrange the buffer
	// if the entry pointer is NULL, no need
	if ( entry->rid.pid == 0 && entry->rid.sid == 0 && entry->key == 0 )
	{
		m_buffer[entry_num * ENTRY_SIZE] = rid.pid;
		m_buffer[entry_num * ENTRY_SIZE + 4] = rid.sid;
		m_buffer[entry_num * ENTRY_SIZE + 8] = key;
	}
	else
	{	char temp[1024];
		memcpy(temp, m_buffer, sizeof(temp));
		
		m_buffer[entry_num * ENTRY_SIZE] = rid.pid;
                m_buffer[entry_num * ENTRY_SIZE + 4] = rid.sid;
                m_buffer[entry_num * ENTRY_SIZE + 8] = key;

		int entry_count = getKeyCount();
		memmove(m_buffer+(entry_num+1)*ENTRY_SIZE, 
			temp+entry_num*ENTRY_SIZE, (entry_count-entry_num)*ENTRY_SIZE);	
	}

	return 0; 
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
	// Point to an entry
	entryStruct* entry;
	entry = (entryStruct *)m_buffer;
	int n_entry = -1;

	while (entry->rid.pid != 0 && entry->rid.sid != 0 && entry->key != 0 )
	{
		n_entry++;

		if ( key >= entry->key)
			entry++;
		else
			break;
	}

	// Check for null node for safefy, shouldn't call 
	// this function if node is empty
	if ( n_entry == -1)
	{
		cout << "The node is empty, please call BTreeNode::insert() " << endl;
		exit(1);
	}

	// Found the position to insert, keep the second half of the
	// entries in temp buffer for splitting
	char temp[1024];
	siblingKey = m_buffer[(n_entry+1) * ENTRY_SIZE + 8];
	memcpy(temp, m_buffer, sizeof(m_buffer));

	// If insertion is in first half
	if ( n_entry * ENTRY_SIZE < 512 )
	{
		// Insert the new record
		m_buffer[n_entry * ENTRY_SIZE] = rid.pid;
		m_buffer[n_entry * ENTRY_SIZE + 4] = rid.sid;
		m_buffer[n_entry * ENTRY_SIZE + 8] = key;

		// Rearrange the buffer
		int entry_count = getKeyCount();
		memmove(m_buffer+(n_entry+1)*ENTRY_SIZE, 
			temp+n_entry*ENTRY_SIZE, (entry_count-n_entry)*ENTRY_SIZE);

		// Erase the second half in m_buffer
		memset(m_buffer+512, 0, 512);

		// Set the second half to sibling
		memcpy(sibling.m_buffer, temp+(n_entry+1)*ENTRY_SIZE, 1020-(n_entry+1)*ENTRY_SIZE);
	}
	else
	{
		// Erase the second half of m_buffer
		memset(m_buffer+512, 0, 1020-512);

		// Set the second half to sibling
		memcpy(sibling.m_buffer, temp+512, 1020-512);
	}

	// Insert the sibling by calling its own insert function
	if ( n_entry * ENTRY_SIZE >= 512)
		sibling.insert(key, rid);

	return 0; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	int entryID = 0;	

	// Entries within a page
	while (entryID * ENTRY_SIZE + 8 <= 1020)
	{
		if ( m_buffer[entryID * ENTRY_SIZE + 8] >= searchKey)
		{
			eid = entryID;
			return 0;
		}
		entryID++;

	}
	// Cannot find a match
	return -1; 
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	// Parse the memory buffer
	rid.pid = m_buffer[eid * ENTRY_SIZE];
	rid.sid = m_buffer[eid * ENTRY_SIZE + 4];
	key = m_buffer[eid * ENTRY_SIZE + 8];

	return 0; 
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	return m_buffer[PAGEID_INDEX];
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
	// Set the pid
	m_buffer[PAGEID_INDEX] = pid;
	return 0; 
}


/*********************************************************
 * 						 	 *
 *		END OF LEAF NODES			 *
 *							 *
**********************************************************/		

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
	if (pf.read(pid, m_buffer) != 0)
	{
		cout << "Error reading from the page file in non leaf" << endl;
		exit(1);
	}

	return 0; 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	if (pf.write(pid, m_buffer) != 0)
	{
		cout << "Error writing to the page file in non leaf" << endl;
		exit(1);
	}
	
	return 0; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
	int count = 0;
	nonLeafEntry* entry = (nonLeafEntry*)m_buffer;

	while(entry->pid !=0 && entry->key != 0)
	{
		count++;
		entry++;
	}

	return count; 
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
	// point an entryStruct to the buffer and start traversing
	nonLeafEntry* entry = (nonLeafEntry *)m_buffer;
	int n_entry = -1;
	while ( entry->key != 0 && entry->pid != 0 )
	{
		n_entry++;

		if ( key >= entry->key)
			entry++;
		else
			break;
	}

	// If the node is empty
	if ( n_entry == -1)
	{
		m_buffer[0] = pid;
		m_buffer[4] = key;
	}
	// If we don't need to rearrange the node
	else if ( entry->key == 0 && entry->pid == 0)
	{
		m_buffer[n_entry * NON_LEAF_ENTRY_SIZE] = pid;
		m_buffer[n_entry * NON_LEAF_ENTRY_SIZE] = key;
	}
	else
	{
		// Point the entryStruct to the buffer and
		// Get the total key counts in node
		nonLeafEntry* ptr = (nonLeafEntry *)m_buffer;
		int count = getKeyCount();
	
		// Save the node to a temp buffer
		char temp[1024];
		memcpy(temp, m_buffer, 1024);
	
		m_buffer[n_entry * NON_LEAF_ENTRY_SIZE] = pid;
		m_buffer[n_entry * NON_LEAF_ENTRY_SIZE] = key;

		int offset = (n_entry+1) * NON_LEAF_ENTRY_SIZE;
		memmove(m_buffer+offset, temp+n_entry*NON_LEAF_ENTRY_SIZE, 
				(count-n_entry)*NON_LEAF_ENTRY_SIZE);
	}

	return 0; 
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	// Point to the entry
	nonLeafEntry* entry = (nonLeafEntry *)m_buffer;
	int n_entry = -1;

	while( entry->pid != 0 && entry->key != 0 )
	{
		n_entry++;

		if ( key >= entry->key)
			entry++;
		else
			break;
	}

	// Check for null node for safety, shouldn't call this
	// function if node is empty
	if ( n_entry == -1)
	{
		cout << "The non-leaf node is empty, please call BTNonLeafNode::insert() " << endl;
		exit(1);
	}
	
	// Found teh position to insert, keep the second half of the
	// entries in temp buffer
	char temp[1024];
	memcpy(temp, m_buffer, sizeof(m_buffer));

	// Determine the middle key
	if ( entry->pid == 0 && entry->key == 0)
		midKey = m_buffer[1012];
	else
		midKey = key;

	// If insertion is in first half
	if ( n_entry * NON_LEAF_ENTRY_SIZE < 512)
	{
		int count = getKeyCount();

		// Insert the pair (pid, key)
		m_buffer[n_entry * NON_LEAF_ENTRY_SIZE] = pid;
		m_buffer[n_entry * NON_LEAF_ENTRY_SIZE] = key;

		// Rearrange the buffer
		memmove(m_buffer+(n_entry+1)*NON_LEAF_ENTRY_SIZE, 
			temp+n_entry*NON_LEAF_ENTRY_SIZE, 1016-(n_entry+1)*NON_LEAF_ENTRY_SIZE);

		// Erase the second half in m_buffer
		memset(m_buffer+512, 0, 512);

		// Set the second half to sibling
		memcpy(sibling.m_buffer, temp+(n_entry+1)*ENTRY_SIZE, 
			1020-(n_entry+1)*NON_LEAF_ENTRY_SIZE);
	}
	else
	{
		// Erase the second half of m_buffer
		memset(m_buffer+512, 0, 1016-512);

		// Set the second half to sibling
		memcpy(sibling.m_buffer, temp+512, 1020-512);
	}

	// Insert the sibling by calling its own insert function
	if ( n_entry * NON_LEAF_ENTRY_SIZE >= 512)
		sibling.insert(pid, key);

	return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
	// Parse the memory buffer
	nonLeafEntry *entry = (nonLeafEntry *)m_buffer;

	while ( entry->pid != 0 && entry->key != 0 )
	{
		if ( searchKey == entry->key )
		{
			pid = entry->pid;
			return 0;
		}
	
		entry++;
	}

	// Cannot find an entry;
	return -1; 
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
	// Modify the buffer to contain pid1, key, pid2
	m_buffer[0] = pid1;
	m_buffer[4] = key;
	m_buffer[8] = pid2;

	return 0; 
}


/************************
 *	End of file	*
 ***********************/
